package dp.practice5;

public class Main1 {
    public static void main(String[] args) {
        System.out.println(minimumComb(15));
    }

    /**
     * BF方法
     *
     * @param w 钱数
     * @return 最小面值组合的数量
     */
    private static int minimumComb(int w) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i <= w / 11; i++)
            for (int j = 0; j <= w / 5; j++)
                for (int k = 0; k <= w; k++)
                    if (11 * i + 5 * j + k == w) {
                        System.out.printf("方案：\n11面值：%d，5面值：%d，1面值：%d\n", i, j, k);
                        if (min > i + j + k) {
                            min = i + j + k;
                        }
                        break;
                    }
        return min;
    }
}
